package sort;

import java.util.Arrays;
import java.util.Random;

public class MergetSort {
    public static void main(String[] args) {
        Random r= new Random(47);
        int[] arr = new int[1000000];
        for(int i =0;i<1000000;i++){
            arr[i]=r.nextInt();
        }
        int[] temp = new int[arr.length];
        long l1 = System.currentTimeMillis();
        sort(arr,0,arr.length-1,temp);
        long l2 = System.currentTimeMillis();
        System.out.println("耗时:"+(l2-l1));
     //   System.out.println(Arrays.toString(arr));
    }
    private static void sort(int [] arr,int left,int rigth,int[] temp){
        if(left<rigth){
            int mid = (left+rigth)/2;
            sort(arr,left,mid,temp);
            sort(arr,mid+1,rigth,temp);
       /*     for(int i =left;i<=mid;i++){
                System.out.print(arr[i]+" ");
            }
            System.out.print("    ");
            for(int i =mid+1;i<=rigth;i++){
                System.out.print(arr[i]+" ");
            }
            System.out.println();*/
            merget(arr,left,mid,rigth,temp);
        }
    }

    private static void merget(int[] arr, int left, int mid, int rigth, int[] temp) {
        int i = left;
        int x=mid+1;
        int index=0;
        while(i<=mid&&x<=rigth){
            if(arr[i]<arr[x]){
                temp[index]=arr[i];
                i++;
                index++;
            }else {
                temp[index]=arr[x];
                x++;
                index++;
            }
        }
            while(i<=mid){
                temp[index]=arr[i];
                index++;
                i++;
            }
        while(x <=rigth){
            temp[index]=arr[x];
            index++;
            x++;
        }
//        System.out.println("temp="+Arrays.toString(temp));
        i=left;
        for (int j=0;j<index;j++){
            arr[i]=temp[j];
            i++;
        }

    }

}
